/*
 * @lc app=leetcode.cn id=316 lang=java
 *
 * [316] 去除重复字母
 */

import java.util.Stack;
// @lc code=start
class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        // 记录每个字符出现的次数
        int[] count = new int[256];
        // 记录字符是否在栈中
        boolean[] inStack = new boolean[26];

        
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }

        for(char c : s.toCharArray()) {
            // 每遍历一个字符，将其出现次数减一
            count[c]--;
            if(inStack[c]) {
                continue;
            }

            while(!stack.isEmpty() && stack.peek() > c) {
                // 当栈顶元素大于当前元素，且栈顶元素后面还有相同元素时，出栈
                if(count[stack.peek()] == 0) {
                    break;
                }
                inStack[stack.pop()] = false;
            }

            stack.push(c);
            inStack[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}
// @lc code=end

